We are given an array nums of positive integers, and two positive integers left and right (left <= right).
Return the number of (contiguous, non-empty) subarrays such that the value of the maximum array element in that subarray is at least left and at most right.
Example: Input: nums = [2, 1, 4, 3] left = 2 right = 3 Output: 3 Explanation: There are three subarrays that meet the requirements: [2], [2, 1], [3].
Note:
left,right, andnums[i]will be an integer in the range[0, 109].- The length of
numswill be in the range of[1, 50000].
Average Rating: 4.22 (32 votes)
Approach #1: Counting [Accepted]
Intuition
We can make the following logical steps to arrive at the solution:
As we only care about whether each element is less than, between, or greater than the interval [L, R], let's pretend each element is either 0 if it is less than L; 1 if it is between L and R; or 2 if it is greater than R.
Then, we want the number of subarrays with no 2 and at least one 1. The 2s split the array into groups of arrays with only 0s and 1s. For example, if our array is [0, 0, 1, 2, 2, 1, 0, 2, 0], then the answer is just the answer for [0, 0, 1] plus the answer for [1, 0] plus the answer for [0].
For each such group (arrays of only 0s or 1s), to count the number of subarrays that have at least one 1, let's count all the subarrays in the group, minus the subarrays that only have zeroes.
For example, [0, 0, 1] has 6 subarrays, 3 of which are zero-only, which adds 3 to the answer; [1, 0] has 3 subarrays, 1 of which is zero-only, which adds 2 to the answer; and [0] has 1 subarray, 1 of which is zero-only, which adds 0 to the answer. The final answer to the previous original example of A = [0, 0, 1, 2, 2, 1, 0, 2, 0] is 3 + 2 + 0 = 5.
Algorithm
Say count(B) is the number of subarrays that have all elements less than or equal to B. From the above reasoning, the answer is count(R) - count(L-1).
How do we compute count(B)? We remember cur, the number of contiguous, previous elements less than or equal to B. When we see a new element less than or equal to B, the number of valid subarrays ending at this position is cur + 1. When we see a new element greater than B, the number of valid subarrays ending at this position is 0.
Complexity Analysis
-
Time Complexity: O(N), where N is the length of
A. -
Space Complexity: O(1).
Last Edit: 15 hours ago
Paid subscription doesn't worth it just because of the articles like this one. You will find much better solutions in the discussion section.
March 5, 2018 9:45 AM
I don't understand why count(B) will work?
2 hours ago
This is such a deceptive problem . At first looks like an Easy Sliding window, but is actually a hard one
10 hours ago
cool math proof
15 hours ago
It's better to include the dp approach where dp[i] = number of valid subarrays ending with i. And then based on 3 cases perform the dp update:
if arr[i] < left => dp[i] = dp[i-1]
else if arr[i] > right => dp[i] = 0, prev = i // initially previous will be -1
else dp[i] = i-prev
Finally answer is sum of all dp[i];
March 5, 2018 9:46 AM
ans += cur; is so weird.
I don't know how to figure it out. And there is no explanation for this.
9 hours ago
I solved the question using backtracking , complexity is like real bad but got accepted.
Still trying to learn dp so here's my take on it.
class Solution {
int solution =0;
public int numSubarrayBoundedMax(int[] nums, int left, int right) {
/* Adding the max element to know wether we already have an element in the array and
that element value is >= left and <= right*/
backTrack(nums,left,right,0,Integer.MIN_VALUE);
return solution;
}
public void backTrack(int[] nums, int left, int right,int index,int max)
{
if(max>= left && max <=right)
solution++;
for(int i=index;i<nums.length;i++)
{
if((nums[i] >= left && nums[i]<=right) || nums[i]<left)
{
backTrack(nums,left,right,i+1,Math.max(max,nums[i]));
/* this is to break when we come out of array such as
for {2,1,3,4} [2,1] is an array but once it backtracks, removes 1
and tries to add 3 to form [2,3], the below condition would truncate the flow*/
if(max!=Integer.MIN_VALUE)
break;
}
/* for Example {2,1,3,4} left =2, right=3 here we are breaking if we try to add 4 to an existing array,
if the array is empty then we will move to the next element in the array */
else if(nums[i] > right && max!=Integer.MIN_VALUE)
break;
else
continue;
}
}
}
Complexity is quite bad, just wanted to add a different way to do the problem.
Last Edit: 12 hours ago
Just read the Algorithm section makes more sense to me:
Find the number of subarrays count(R) whose maximum element is no larger than R and similarly count(L-1).
count(R) - count(L-1) by definition is the number of subarrays whose max is between L and R inclusive.
Last Edit: June 12, 2021 9:41 PM
This question could be Hard
Count of Subarrays in range (L, R] => Count of Subarrays at most R - Count of Subarrays at most L
Similar questions:
1248:
public int numberOfSubarrays(int[] A, int K) {
return atMostK(A, K) - atMostK(A, K - 1);
}
private int atMostK(int[] A, int K) {
int ans = 0;
int count = 0;
for(int l = 0, r = 0; r < A.length; r++) {
count += A[r] % 2;
while(count > K) {
count -= A[l] % 2;
l++;
}
ans += r - l + 1;
}
return ans;
}
992:
public int subarraysWithKDistinct(int[] A, int K) {
return atMostK(A, K) - atMostK(A, K - 1);
}
private int atMostK(int[] A, int K) {
int ans = 0;
HashMap<Integer, Integer> map = new HashMap<>();
for(int i = 0, j = 0; j < A.length; j++) {
map.put(A[j], map.getOrDefault(A[j], 0) + 1);
while(map.size() > K) {
int count = map.get(A[i]);
if(count == 1) map.remove(A[i]);
else map.put(A[i], count - 1);
i++;
}
ans += j - i + 1;
}
return ans;
}
You don't have any submissions yet.
xxxxxxxxxxclass Solution {public: int numSubarrayBoundedMax(vector<int>& nums, int left, int right) { }};